package com.datastructure.test.isentireandsearchbinarytree;


import java.util.ArrayList;
import java.util.LinkedList;

public class IsEntireAndSearchBinaryTree {

    public static void main(String[] args) {

    }

    public boolean[] judgeIt (TreeNode root) {
        // write code here
        boolean[] data = new boolean[2];
        data[0]=isSearchBinaryTree(root);
        data[1]= root == null || isCompleteTree(root);
        return data;
    }

    public boolean isSearchBinaryTree(TreeNode root){
        if(root==null){
            return true;
        }
        ArrayList<Integer> data = new ArrayList<>();
        inOrder(root,data);
        for (int i = 0; i < data.size()-1; i++) {
            if(data.get(i)>data.get(i+1)){
                return false;
            }
        }
        return true;
    }

    public boolean isCompleteTree (TreeNode root) {
        // write code here
        if (root == null) {
            return true;
        }

        // 使用层序遍历的思路，进行遍历，只是不需要判断left和right是否为null
        // 如果前面出现了null，后面又有非null的情况，那么就不是完全二叉树
        LinkedList<TreeNode> list = new LinkedList();
        list.offer(root);
        boolean hasNull = false;
        while (!list.isEmpty()) {
            TreeNode currentNode = list.poll();
            if (currentNode == null) {
                hasNull = true;
            } else {
                if (hasNull) return false;

                list.offer(currentNode.left);
                list.offer(currentNode.right);
            }
        }

        return true;}

    private void inOrder(TreeNode root, ArrayList<Integer> data) {
        if(root==null){
            return;
        }
        inOrder(root.left,data);
        data.add(root.val);
        inOrder(root.right,data);
    }
}

class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;
  }
